package com.atwisdom.star.common.tree;

import cn.hutool.core.util.StrUtil;
import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 
 * @Date: 2023-04-20 12:02
 */
@Slf4j
public class TreeHelper {

    /**
     * 广度优先
     *
     * @param root
     */
    public static <T> List<TreeNode<T>> breadthFirst(TreeNode root) {
        List<TreeNode<T>> resultList = new ArrayList<>();
        Deque<TreeNode> nodeDeque = new LinkedList<>();
        TreeNode node = root;
        nodeDeque.add(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.pop();
            resultList.add(node);
            nodeDeque.addAll(node.getChildren());
        }
        log.info("breadthFirst result begin<---------->");
        log.info(resultList.stream().map(d->d.getId()).collect(Collectors.joining("-->")));
        log.info("breadthFirst result end<---------->");
        return resultList;
    }

    /**
     * 深度优先
     * @param root
     */
    public static <T> List<TreeNode<T>> depthFirst(TreeNode root) {
        List<TreeNode<T>> resultList = new ArrayList<>();
        Deque<TreeNode> nodeDeque = new LinkedList<>();
        TreeNode node = root;
        nodeDeque.push(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.pop();
            resultList.add(node);
            List<TreeNode> children = node.getChildren();
            for (int i = children.size() - 1; i >= 0; i--) {
                nodeDeque.push(children.get(i));
            }
        }
        log.info("depthFirst result begin<---------->");
        log.info(resultList.stream().map(d->d.getId()).collect(Collectors.joining("-->")));
        log.info("depthFirst result end<---------->");
        return resultList;
    }


    /**
     * 判断节点在分支上是否存在
     * @param node
     * @return
     */
    public static boolean existInAncestry(TreeNode node) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.push(node);
        TreeNode current = node.getParent();
        while(current != null){
            deque.push(current);
            if (StrUtil.equals(node.getId(), current.getId())) {
                log.error("树中出现了循环引用");
                log.error(deque.stream().map(d->d.getId()).collect(Collectors.joining("-->")));
                return true;
            }
            current = current.getParent();
        }
        return false;
    }

    /**
     * 节点在树中是否存在
     * @param root
     * @param id
     * @return
     */
    public static boolean exist(TreeNode root, String id) {
        return findById(root, id) != null;
    }


    /**
     * 查找某个节点
     **/
    public static TreeNode findById(TreeNode root, String id) {
        if (null == root) {
            return null;
        } else {
            if (id.equals(root.getId())) {
                return root;
            } else {
                List<TreeNode> childList = root.getChildren();
                if (null != childList) {
                    for (TreeNode child : childList) {
                        TreeNode result = findById(child, id);
                        if (result != null) {
                            return result;
                        }
                    }
                }
                return null;
            }
        }
    }


    /**
     * 前序遍历
     * @param root
     * @return
     */
    public static <T> List<TreeNode> preorder(TreeNode<T> root) {
        List<TreeNode> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode<T> node = stack.pop();
            res.add(node);
            for (int i = node.getChildren().size() - 1; i >= 0; i--) {
                stack.push(node.getChildren().get(i));
            }
        }
        return res;
    }


    public static List<TreeNode> inorder(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        inorderTraversalInter(result, root);
        return result;
    }

    private static <T> void inorderTraversalInter(List<TreeNode> result, TreeNode<T> root) {
        if (root == null){
            return ;
        }
        inorderTraversalInter(result, root.getChildren().size() != 0 ? root.getChildren().get(0) : null);
        result.add(root);
        List<TreeNode<T>> children = root.getChildren();
        if (children.size()>1) {
            for (int i = 1; i < children.size(); i++) {
                inorderTraversalInter(result, children.get(i));
            }
        }
    }

    public static <T> List<TreeNode> postorder(TreeNode<T> root) {
        LinkedList<TreeNode> res = new LinkedList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode<T> node = stack.pop();
            res.addFirst(node);
            for (TreeNode child : node.getChildren()) {
                if (child != null) {
                    stack.push(child);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<Integer>("1", null);
        TreeNode<Integer> root11 = new TreeNode<Integer>("2", root);
        TreeNode<Integer> root12 = new TreeNode<Integer>("3", root);
        root.addChild(root11);
        root.addChild(root12);
        TreeNode<Integer> root111 = new TreeNode<Integer>("4", root11);
        TreeNode<Integer> root112 = new TreeNode<Integer>("5", root11);
        TreeNode<Integer> root113 = new TreeNode<Integer>("6", root11);
        root11.addChild(root111);
        root11.addChild(root112);
        root11.addChild(root113);
        List<TreeNode> preorder = preorder(root);
        List<TreeNode> inorder = inorder(root);
        List<TreeNode> postorder = postorder(root);
        System.out.println();
    }

}

